#include <bits/stdc++.h>
using namespace std;

class Solution {
    public:
        // int profitableSchemes(int n, int m, vector<int>& group, vector<int>& profit) {
        //     int sz = group.size(), MOD = 1e9 + 7;
        //     vector<vector<vector<int>>> dp(sz+1, vector<vector<int>>(n+1, vector<int>(m+1)));
        //     dp[0][0][0] = 1;
        //     for(int i = 1; i <= sz; i++)
        //     {
        //         for(int j = 0; j <= n; j++)
        //         {
        //             for(int k = 0; k <= m; k++)
        //             {
        //                 dp[i][j][k] = dp[i-1][j][k];
        //                 if(j >= group[i-1]) dp[i][j][k] = (dp[i][j][k] + dp[i-1][j-group[i-1]][max(0, k-profit[i-1])]) % MOD;
        //             }
        //         }
        //     }
        //     int sum = 0;
        //     for (int j = 0; j <= n; j++) {
        //         sum = (sum + dp[sz][j][m]) % MOD;
        //     }
        //     return sum;
        // }
    
        int profitableSchemes(int n, int m, vector<int>& group, vector<int>& profit) {
            int sz = group.size(), MOD = 1e9 + 7;
            vector<vector<int>> dp(n+1, vector<int>(m+1));
            dp[0][0] = 1;
            for(int i = 1; i <= sz; i++)
            {
                for(int j = n; j >= group[i-1]; j--)
                {
                    for(int k = m; k >= 0; k--)
                    {
                        dp[j][k] = (dp[j][k] + dp[j-group[i-1]][max(0, k-profit[i-1])]) % MOD;
                    }
                }
            }
            int sum = 0;
            for (int j = 0; j <= n; j++) {
                sum = (sum + dp[j][m]) % MOD;
            }
            return sum;
        }
    };